
/**
 * 一条包含字母 A-Z 的消息通过以下方式进行了编码：
 * <p>
 * 'A' -> 1
 * 'B' -> 2
 * ...
 * 'Z' -> 26
 * 给定一个只包含数字的非空字符串，请计算解码方法的总数。
 * <p>
 * 示例 1:
 * <p>
 * 输入: "12"
 * 输出: 2
 * 解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
 * 示例 2:
 * <p>
 * 输入: "226"
 * 输出: 3
 * 解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
 */
class Solution {

    public static void main(String[] args) {
        System.out.println(numDecodings2("111"));
    }

    private static int[] dp;

    public static int numDecodings(String s) {
        dp = new int[s.length()];
        return numDecodings(s.toCharArray(), 0);
    }

    public static int numDecodings(char[] chars, int i) {
        if (i >= chars.length) return 1;
        int res;
        if (dp[i] != 0) {
            return dp[i];
        }
        if (chars[i] == '1') {
            if (i + 1 == chars.length) {
                res = 1;
            } else {
                res = numDecodings(chars, i + 1) + numDecodings(chars, i + 2);
            }
        } else if (chars[i] == '2') {
            if (i + 1 == chars.length) {
                res = 1;
            } else if (chars[i + 1] <= '6') {
                res = numDecodings(chars, i + 1) + numDecodings(chars, i + 2);
            } else {
                res = numDecodings(chars, i + 1);
            }
        } else if (chars[i] == '0') {
            res = 0;
        } else {
            res = numDecodings(chars, i + 1);
        }
        dp[i] = res;
        return res;
    }

    /**
     * 从最后一个开始反推，推到最前面，最核心的是dp[i] = dp[i + 1] + dp[i + 2];
     *
     * @param s
     * @return
     */
    public static int numDecodings2(String s) {
        char[] chars = s.toCharArray();
        dp = new int[s.length()];
        dp[s.length() - 1] = 1;
        if (chars[s.length() - 1] == '0') {
            dp[s.length() - 1] = 0;
        }
        int i = s.length() - 2;
        if (chars[i] == '1') {
            dp[i] = dp[i + 1] + 1;
        } else if (chars[i] == '2') {
            if (chars[i + 1] <= '6') {
                dp[i] = dp[i + 1] + 1;
            } else {
                dp[i] = dp[i + 1];
            }
        } else if (chars[i] == '0') {
            dp[i] = 0;
        } else {
            dp[i] = dp[i + 1];
        }
        for (i = s.length() - 3; i >= 0; i--) {
            if (chars[i] == '0') {
                dp[i] = 0;
            } else if (chars[i] == '1') {
                dp[i] = dp[i + 1] + dp[i + 2];
            } else if (chars[i] == '2') {
                if (chars[i + 1] <= '6') {
                    dp[i] = dp[i + 1] + dp[i + 2];
                } else {
                    dp[i] = dp[i + 1];
                }
            } else {
                dp[i] = dp[i + 1];
            }
        }
        return dp[0];
    }


}